/**
 * 通配符匹配
 *
 * 给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
 * '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符序列（包括空字符序列）。
 * 判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
 *
 * 示例 1：
 * 输入：s = "aa", p = "a"
 * 输出：false
 * 解释："a" 无法匹配 "aa" 整个字符串。
 * 示例 2：
 * 输入：s = "aa", p = "*"
 * 输出：true
 * 解释：'*' 可以匹配任意字符串。
 * 示例 3：
 * 输入：s = "cb", p = "?a"
 * 输出：false
 * 解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
 *
 * 提示：
 * 0 <= s.length, p.length <= 2000
 * s 仅由小写英文字母组成
 * p 仅由小写英文字母、'?' 或 '*' 组成
 */

/**
 * 这一题和之前的 10.正则表达式匹配 差不多一样, 这一题反而还是更简单一点的
 * 动态规划 dp[i][j] : s 的前 i个 是否可以用 p的前 j个匹配
 * 1. p[j] == '?' : dp[i][j] = dp[i - 1][j - 1]
 * 2. p[j] == '*' : 匹配空串 : dp[i][j] = dp[i][j - 1]
 *                  匹配一个后还可以匹配 : dp[i][j] = dp[i - 1][j]
 * 3. p[j] == '普通字符' : s[i] == p[j] : dp[i][j] = dp[i - 1][j - 1];
 *                       s[i] != p[j] : dp[i][j] = false;
 *
 * 时间复杂度 : O(m * n)
 * 空间复杂度 : O(m * n)
 */

public class Main {
    public boolean isMatch(String s, String p) {

        // 字符串长度
        int m = s.length(), n = p.length();

        // dp数组
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 初始化, 我们的两个字符串啥也没有时为 true
        dp[0][0] = true;

        // 这里要是能碰到 * 也是true, 这里要是前面有 别的字符, 也是直接不为 true了
        // 因为前面的 通过 * 匹配不掉
        for (int i = 1; i <= n; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                // 这里就是上面的动态规划
                if (p.charAt(j - 1) == '?') {

                    dp[i][j] = dp[i - 1][j - 1];

                } else if (p.charAt(j - 1) == '*') {

                    dp[i][j] = dp[i][j - 1];
                    dp[i][j] |= dp[i - 1][j];

                } else {

                    if (p.charAt(j - 1) == s.charAt(i - 1)) {

                        dp[i][j] = dp[i - 1][j - 1];

                    } else {

                        dp[i][j] = false;

                    }
                }
            }
        }

        // 最后返回 dp 的 最后一个位置, 看看整个 s, p 匹不匹配
        return dp[m][n];
    }
}